package 单周赛.history;

import util.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 *
 */
public class 第300场单周赛 {

    public static void main(String[] args) {

        System.out.println(decodeMessage("the quick brown fox jumps over the lazy dog", "vkbs bs t suepuv"));


        ListNode node0 = new ListNode(0);
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        node0.next = node1;
        node1.next = node2;
        spiralMatrix(2, 2, node0);

        System.out.println(peopleAwareOfSecret(6, 2, 4));
    }

    /**
     * 模拟
     * 用哈希表存储密文和明文的对应关系
     *
     * @param key
     * @param message
     * @return
     */
    public static String decodeMessage(String key, String message) {
        StringBuilder stringBuilder = new StringBuilder();
        Map<Character, Character> map = new HashMap<>();
        int index = 0;
        for (int i = 0; i < key.length() && index < 26; i++) {
            char keyChar = key.charAt(i);
            if (keyChar == ' ') continue;
            if (!map.containsKey(keyChar)) {
                map.put(keyChar, (char) (index + 'a'));
                index++;
            }
        }
        map.put(' ', ' ');
        for (int i = 0; i < message.length(); i++) {
            stringBuilder.append(map.get(message.charAt(i)));
        }
        return stringBuilder.toString();
    }

    /**
     * 模拟
     * 定义四个方向
     * 向右 -> 向下 -> 向左 -> 向上 -> 向右
     * 先向右走，如果超出边界或者右边已经赋值成功过，则改变方向
     *
     * @param m
     * @param n
     * @param head
     * @return
     */
    public static int[][] spiralMatrix(int m, int n, ListNode head) {
        int[][] matrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = -1;
            }
        }
        boolean right = true, down = false, left = false, up = false;
        int row = 0, column = 0;
        while (head != null) {
            if (right) {
                matrix[row][column] = head.val;
                column++;
                if (column == n || matrix[row][column] != -1) {
                    right = false;
                    down = true;
                    column--;
                    row++;
                }
            } else if (down) {
                matrix[row][column] = head.val;
                row++;
                if (row == m || matrix[row][column] != -1) {
                    down = false;
                    left = true;
                    row--;
                    column--;
                }
            } else if (left) {
                matrix[row][column] = head.val;
                column--;
                if (column == -1 || matrix[row][column] != -1) {
                    left = false;
                    up = true;
                    column++;
                    row--;
                }
            } else if (up) {
                matrix[row][column] = head.val;
                row--;
                if (row == -1 || matrix[row][column] != -1) {
                    up = false;
                    right = true;
                    row++;
                    column++;
                }
            }
            head = head.next;
        }
        return matrix;
    }

    /**
     * 动态规划
     * 用一个哈希表存储
     * key 表示第几天，value表示第几天有几个人
     *
     * @param n
     * @param delay
     * @param forget
     * @return
     */
    public static int peopleAwareOfSecret(int n, int delay, int forget) {
        Map<Integer, Integer> preMap = new HashMap<>();
        preMap.put(1, 1);
        for (int i = 2; i <= n; i++) {
            Map<Integer, Integer> curMap = new HashMap<>();
            for (Integer day : preMap.keySet()) {
                // 超过忘记的天数
                if (day + 1 > forget) continue;
                // 只要延迟delay天之后，每天都会分享一个新人
                if (day + 1 > delay) {
                    int people = curMap.getOrDefault(1, 0) + preMap.get(day);
                    if (people >= 1000000007) people -= 1000000007;
                    curMap.put(1, people);
                }
                // 上一天加上今天，上一天有多少人，表示今天也有多少人
                curMap.put(day + 1, preMap.get(day));
            }
            preMap = curMap;
        }
        long ans = 0;
        for (Integer day : preMap.keySet()) {
            ans += preMap.get(day);
            if (ans >= 1000000007) ans -= 1000000007;
        }
        return (int) ans;
    }

}
